﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace ImryStefanVRPprogram
{
    public class NeighboorhoodSearches
    {
        /// <summary>
        /// Finds a single good move in the neighborhood. Returns the change so it is possible to undo.
        /// </summary>
        internal static ChangeInSolution GetGoodSolutionInANeighborhood(CVRPSolution currentSolution)
        {
            List< ChangeInSolution> theList = new List<ChangeInSolution>();

            for (int ok = 0; ok < Program.vrpData.Dimension * Program.vrpData.Dimension; ok++) // Choose 1st route
            {
                int i = Program.rand.Next(currentSolution.listOfRoutes.Count);
                int j = Program.rand.Next(currentSolution.listOfRoutes.Count);
                if (i != j)
                {
                    int k = 1 + Program.rand.Next(currentSolution.listOfRoutes[i].GetNumberOfNodesVisited());
                    int l = 1 + Program.rand.Next(currentSolution.listOfRoutes[j].GetNumberOfNodesVisited());

                    // Swaps work only if the both nodes chosen are not depots. Also they are symmetric
                    if (i < j && l <= currentSolution.listOfRoutes[j].GetNumberOfNodesVisited() && k <= currentSolution.listOfRoutes[i].GetNumberOfNodesVisited())
                    {
                        ChangeInSolution aSwap = GenerateAswap(i, j, k, l, currentSolution);
                        if (aSwap.thisMoveType != MoveType.NoMove)
                        {
                            for (int listIndex = 0; listIndex < theList.Count; listIndex++)
                            {
                                if (theList[listIndex].totalCostAfterChange > aSwap.totalCostAfterChange)
                                {
                                    theList.Insert(listIndex, aSwap);
                                    break;
                                }
                            }
                            if (theList.Count == 0)
                                theList.Add(aSwap);
                        }
                    }

                    // Injections into 2nd route require starting with a node which is not a depot
                    if (k <= currentSolution.listOfRoutes[i].GetNumberOfNodesVisited())
                    {
                        ChangeInSolution anInjection = GenerateAnInjection(i, j, k, l, currentSolution);
                        if (anInjection.thisMoveType != MoveType.NoMove)
                        {
                            for (int listIndex = 0; listIndex < theList.Count; listIndex++)
                            {
                                if (theList[listIndex].totalCostAfterChange > anInjection.totalCostAfterChange)
                                {
                                    theList.Insert(listIndex, anInjection);
                                    break;
                                }
                            }
                            if (theList.Count == 0)
                                theList.Add(anInjection);
                        }
                    }
                }
                if (theList.Count == 20)
                    theList.RemoveAt(19);
            }
            if (theList.Count > 0)
            {
                // Generate a Poisson Random Variable with mean 1
                double p = 1, L = Math.Exp(-1);
                int k = 0;
                do
                {
                    k++;
                    p = Program.rand.NextDouble();
                }
                while (p > L);

                ChangeInSolution theChangeToBeMade = theList[Math.Min(k - 1, theList.Count() - 1)];
                currentSolution.ApplyChange(theChangeToBeMade);
                return theChangeToBeMade;
            }
            else
                return new ChangeInSolution(currentSolution.totalCost);
        }

        /// <summary>
        /// A random perturbation of the solution. Not possible to undo, so it doesn't return anything.
        /// </summary>
        internal static void HugeJump(CVRPSolution currentSolution)
        {
            for (int ok = 0; ok < Math.Sqrt(Program.vrpData.Dimension); ok++)
            {
                int i = Program.rand.Next(currentSolution.listOfRoutes.Count);
                int j = Program.rand.Next(currentSolution.listOfRoutes.Count);
                if (i < j)
                {
                    int k = 1 + Program.rand.Next(currentSolution.listOfRoutes[i].GetNumberOfNodesVisited() - 1);
                    int l = 1 + Program.rand.Next(currentSolution.listOfRoutes[j].GetNumberOfNodesVisited() - 1);

                    ChangeInSolution aSwap = GenerateAswap(i, j, k, l, currentSolution);

                    if (aSwap.thisMoveType == MoveType.Swap)
                        currentSolution.ApplyChange(aSwap);
                }
            }
        }

        private static ChangeInSolution GenerateAswap(int i, int j, int k, int l, CVRPSolution currentSolution)
        {
            ChangeInSolution aSwap = new ChangeInSolution(currentSolution.totalCost);

            aSwap.nextDemandOnA = currentSolution.listOfRoutes[i].totalDemandOnRoute - Program.vrpData.Demands[currentSolution.listOfRoutes[i].GetNodeAt(k)] + Program.vrpData.Demands[currentSolution.listOfRoutes[j].GetNodeAt(l)];
            aSwap.nextDemandOnB = currentSolution.listOfRoutes[j].totalDemandOnRoute - Program.vrpData.Demands[currentSolution.listOfRoutes[j].GetNodeAt(l)] + Program.vrpData.Demands[currentSolution.listOfRoutes[i].GetNodeAt(k)];

            if (aSwap.nextDemandOnA <= Program.vrpData.Capacity &&
               aSwap.nextDemandOnB <= Program.vrpData.Capacity)
            {
                aSwap.thisMoveType = MoveType.Swap;
                aSwap.prevDemandOnA = currentSolution.listOfRoutes[i].totalDemandOnRoute;
                aSwap.prevDemandOnB = currentSolution.listOfRoutes[j].totalDemandOnRoute;

                aSwap.nextDistOnA = currentSolution.listOfRoutes[i].totalDistanceOfRoute
                    - Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k - 1), currentSolution.listOfRoutes[i].GetNodeAt(k)]
                    - Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k), currentSolution.listOfRoutes[i].GetNodeAt(k + 1)]
                    + Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k - 1), currentSolution.listOfRoutes[j].GetNodeAt(l)]
                    + Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l), currentSolution.listOfRoutes[i].GetNodeAt(k + 1)];
                aSwap.nextDistOnB = currentSolution.listOfRoutes[j].totalDistanceOfRoute
                    - Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l - 1), currentSolution.listOfRoutes[j].GetNodeAt(l)]
                    - Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l), currentSolution.listOfRoutes[j].GetNodeAt(l + 1)]
                    + Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l - 1), currentSolution.listOfRoutes[i].GetNodeAt(k)]
                    + Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k), currentSolution.listOfRoutes[j].GetNodeAt(l + 1)];
                aSwap.prevDistOnA = currentSolution.listOfRoutes[i].totalDistanceOfRoute;
                aSwap.prevDistOnB = currentSolution.listOfRoutes[j].totalDistanceOfRoute;

                aSwap.routeA = i;
                aSwap.routeB = j;
                aSwap.spotA = k;
                aSwap.spotB = l;

                aSwap.totalCostAfterChange = aSwap.totalCostBeforeChange + aSwap.nextDistOnA + aSwap.nextDistOnB - aSwap.prevDistOnA - aSwap.prevDistOnB;
            }
            return aSwap;
        }

        private static ChangeInSolution GenerateAnInjection(int i, int j, int k, int l, CVRPSolution currentSolution)
        {
            ChangeInSolution anInjection = new ChangeInSolution(currentSolution.totalCost);

            anInjection.nextDemandOnA = currentSolution.listOfRoutes[i].totalDemandOnRoute
                                         - Program.vrpData.Demands[currentSolution.listOfRoutes[i].GetNodeAt(k)];
            anInjection.nextDemandOnB = currentSolution.listOfRoutes[j].totalDemandOnRoute
                                         + Program.vrpData.Demands[currentSolution.listOfRoutes[i].GetNodeAt(k)];

            if (anInjection.nextDemandOnB <= Program.vrpData.Capacity)
            {
                if (currentSolution.listOfRoutes[i].GetNumberOfNodesVisited() == 1)
                    anInjection.thisMoveType = MoveType.InjectionWhichRemovesARoute;
                else
                    anInjection.thisMoveType = MoveType.InjectionWhichPerservesBothRoutes;

                anInjection.prevDemandOnA = currentSolution.listOfRoutes[i].totalDemandOnRoute;
                anInjection.prevDemandOnB = currentSolution.listOfRoutes[j].totalDemandOnRoute;

                anInjection.nextDistOnA = currentSolution.listOfRoutes[i].totalDistanceOfRoute
                         + Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k + 1), currentSolution.listOfRoutes[i].GetNodeAt(k - 1)]
                         - Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k), currentSolution.listOfRoutes[i].GetNodeAt(k - 1)]
                         - Program.vrpData.Distances[currentSolution.listOfRoutes[i].GetNodeAt(k + 1), currentSolution.listOfRoutes[i].GetNodeAt(k)];
                anInjection.nextDistOnB = currentSolution.listOfRoutes[j].totalDistanceOfRoute
                         + Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l - 1), currentSolution.listOfRoutes[i].GetNodeAt(k)]
                         + Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l), currentSolution.listOfRoutes[i].GetNodeAt(k)]
                         - Program.vrpData.Distances[currentSolution.listOfRoutes[j].GetNodeAt(l - 1), currentSolution.listOfRoutes[j].GetNodeAt(l)];
                anInjection.prevDistOnA = currentSolution.listOfRoutes[i].totalDistanceOfRoute;
                anInjection.prevDistOnB = currentSolution.listOfRoutes[j].totalDistanceOfRoute;

                anInjection.routeA = i;
                anInjection.routeB = j;
                anInjection.spotA = k;
                anInjection.spotB = l;

                anInjection.totalCostAfterChange = anInjection.totalCostBeforeChange + anInjection.nextDistOnA + anInjection.nextDistOnB - anInjection.prevDistOnA - anInjection.prevDistOnB;
            }
            return anInjection;
        }

    }
}
